

//二叉树的非递归前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
     List<Integer> list=new ArrayList<>();

         if(root==null){
            return list;
        }
      
       TreeNode cur=root;
        Deque<TreeNode> stack=new LinkedList<>();
        while(cur!=null||!stack.isEmpty()){//这个判断比较难想
       while(cur!=null){
           stack.push(cur);
           //System.out.print(cur.val+" ");
           list.add(cur.val);
           cur=cur.left;
       }
       TreeNode top=stack.pop();
       cur=top.right;

        
    }
    return list;
    }
}